The term “component” is used in the field of computer vision to indicate a group of pixels or voxels having one or more common properties. This common property is, for many applications, spatial connectivity. Labeling connected components in a binary image is a fundamental operation in the fields of pattern recognition, computer vision, and medical image analysis. A binary image is converted into a symbolic image, and each connected component is assigned a unique label. There are basically two types of existing methods for labeling connected components: one type is based on label equivalences, and the other is based on contour tracing.
Several algorithms based on label equivalence are proposed for labeling connected components. These include algorithms that repeat passes through an image to propagate label equivalences directly, or indirectly via a provisional label search. A detailed review of these and other related types of algorithms can be found in Suzuki et al [Suzuki, K., Horiba, I., Sugie, N., “Linear-time connected component labeling based on sequential local operations”, Computer Vision and Image Understanding, 2003; 89: 1-23].
Contour tracing techniques are described in Chang et al [Chang, F., Chen, C. J., Lu, C. J., “A linear-time component-labeling algorithm using contour tracing technique”, Computer Vision and Image Understanding, 2004; 93: 206-220]. The two-dimensional (2D) contours are labeled, and only one pass is needed to label inner object pixels.
Both types of techniques have limitations. The number of passes required in label equivalence methods typically depends upon the complexity of the connected components. Similarly, the contour tracing methods are also dependent upon the complexity of the contours involved.
Labeling connected components is fundamentally a recursive operation. Starting from an object pixel or voxel of a component, any neighboring object pixels or voxels belonging to the same component is assigned the same label. Once a neighboring object pixel/voxel is labeled, its neighboring object pixels/voxels are checked and labeled. This procedure continues until all the object pixels/voxels of this component are labeled. Iterative computations are performed, in practice, to label the connected-components. Iterative functions are preferred as they do not consume as much stacked memory.
Nevertheless, iterative approaches to labeling connected components are computationally inefficient. This inefficiency is exacerbated when the images become larger, such as for three-dimensional magnetic resonance imaging (MRI) applications. Improved methods for labeling connected components are thus required in view of these and other observations.